/**
 * Created by sunchenglin on 2017/6/30.
 */
public class BinaryTree {
    // 节点定义
    class Node{
        private int val = 0;
        private Node left = null;
        private Node right = null;
        public Node(int val) {
            this.val = val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public void setRight(Node right) {
            this.right = right;
        }

        public int getVal() {
            return val;
        }

        public Node getLeft() {
            return left;
        }

        public Node getRight() {
            return right;
        }
    }
    //根节点
    private Node root;

    public Node getRoot() {
        return root;
    }

    public void setRoot(Node root) {
        this.root = root;
    }

    BinaryTree(){
        root = null;
    }
    Node buildTree(Node node, int data){
        if (node == null){
            node = new Node(data);
            if(node == null)
                System.out.println("memory error");
        }
        else {
            if(data < node.val){
                node.setLeft(buildTree(node.left,data));
            }else{
                node.setRight(buildTree(node.right, data));
            }
        }
        return node;
    }

    void inOrder(Node node){
        if(node != null){
            if(node.left != null){
                inOrder(node.left);
            }
            System.out.println(node.val);
            if (node.right!=null){
                inOrder(node.right);
            }
        }
    }
    public int TreeDepth(Node root) {
        int left,right;
        if (root == null)
            return 0;
        else{
            left = TreeDepth(root.left);
            right = TreeDepth(root.right);
        }
        return left>right? left+1:right+1;
    }
   public boolean IsBalanced_Solution(Node root) {
        if (root == null)
            return true;
        int leftHeight=0, rightHeight=0;
        leftHeight= TreeDepth(root.left);
        rightHeight = TreeDepth(root.right);
        if (leftHeight-rightHeight>1 || rightHeight-leftHeight>1)
            return false;
        else
            return true;

    }
    public static void main(String args[]){

        BinaryTree tree = new BinaryTree();
        for(int i=1; i<10; i++){
            tree.setRoot(tree.buildTree(tree.getRoot(),i));
        }
        tree.inOrder(tree.getRoot());
        System.out.println(tree.TreeDepth(tree.getRoot()));
    }
}
